'''
https://leetcode.cn/problems/integer-break/

1）
连续情况
n = kx
求 max{ x^(n/x) }
设f(x) = x^(n/x)
方便计算左右同时对数
ln (f(x)) = n/x lnx
求导数，
(1/f(x)) f'(x)= -n(1/x^2)lnx + n/(x^2) = (n/(x^2)) (1-  lnx)
另导数为0求极值，则有x = e
分析单调性：0 < x <e, 则 n/(x^2) > 0, (1-  lnx) > 0.   则导数 > 0, 原函数单调递增
分析单调性：e < x, 则 n/(x^2) > 0, (1-  lnx) < 0.      则导数 < 0，原函数单调递减
可得f(x), 在x=e点去的最大值

2）连续情况，可用离散化+归纳法证明

'''
MOD = 10**9 + 7
class Solution:

    def integerBreak(self, n: int) -> int:
        if n <= 3:
            return n - 1  # 2→1, 3→2
        res = 1
        while n > 4:
            res *= 3 % MOD
            n -= 3
        return res * n % MOD  # 处理剩余的n（2, 3, 或4）

    def integerBreak2(n: int) -> int:
        if n <= 3:
            return n - 1  # 直接处理n=2→1, n=3→2

        q, r = divmod(n, 3)
        if r == 0:
            return 3  ** q % MOD
        elif r == 1:
            return 3  ** (q - 1) * 4 % MOD  # 用4（2×2）替换一个3和1
        else:
            return 3  ** q * 2 % MOD

    # 一定要分成拆成k份
    # 尽量的接近 n/k
    def integerBreak3(n: int, k) -> int:

        q, r = divmod(n, k)
        # r个(q + 1)
        # k-r 个(q)
        return q ** (k-r) + (q+1) ** r
